1. Field of the Invention
The present invention relates to a memory area allocation method in an information processing system.
2. Description of the Related Art
As a method for allocating data, a program or the like, to the free area of a memory space (area allocation method), according to a request from an operating system (OS), an application program, interrupt (external interrupt, exceptional interrupt or instruction interrupt) or the like, a first fit method for allocating the first found allocable memory space and a best fit method for allocating an optimal free area for necessary memory after checking all free areas are well known.
For example, in Japanese Patent Application Publication No. H5-324431, a data area is polarized and allocated in order to efficiently manage memory by minimizing the fragmentation of the free area in internal memory. As its method, a method using the best fit mode and a method using a first fit mode are disclosed.
FIG. 1 explains the best fit method. FIG. 1 shows the memory allocation idea in which used areas 100b, 100d and 100f and free areas 100a, 100c and 100e are mixed. The best fit method allocates a free area closest to a requested size. The requested size is the size of data, a program or the like to be allocated to a free area according to the above-described request.
FIG. 1 shows the case where data 101 is allocated to memory 100. In this case, the memory 100 is retrieved from top to bottom. After retrieving all areas, free areas 100a, 100c and 100e are found. The data 101 is allocated to the smallest free area 100c of free areas with a size sufficient to store the data 101 to allocate.
By using this method, the fragmentation of an area can be suppressed and the area can be efficiently allocated.
FIG. 2 explains the first fit method. FIG. 2 shows the memory allocation idea in which used areas 100b, 100d and 100f and free areas 100a, 100c and 100e are mixed. The first fit method allocates an area first meeting a requested length (requested size) of free areas arranged in addresses order.
FIG. 2 shows the case where the data 101 is allocated to the memory 100. In this case, the memory 100 is retrieved from top to bottom. The data 101 is allocated to the first found free area 100a with a size sufficient to store the data 101 to allocate.
This method emphasizes its retrieval speed. This first fit method has a characteristic of allocating a free space close to the retrieval starting direction. Therefore, by providing a mechanism for retrieving from both low/high directions, an area to be used can be divided according to its usage, thereby preventing the memory area breakdown.
As described above, in Japanese Patent Application Publication No. H5-324431, an allocable free area is searched for from a higher-order area or a lower-order area in the first fit mode or the best fit mode, according to its usage.
However, in the case of the first fit mode, sometimes a larger memory space than a necessary memory space is allocated and there is a problem in the efficiency in use of an area to be used. In the case of best fit mode, it takes too much time since all free areas are checked once.
Furthermore, if in a memory space, an area for storing a program or the like, and an area for storing data or the like are mixed and located, the efficiency in use of memory degrades, which is a problem from the viewpoints of the difference in information characteristic, such as an area size, life or the like. Japanese Patent Application Publication No. H5-324431 has a problem that free areas are scattered in a toothless shape although the memory area is polarized allocated.
As described above, the prior art has both merits/demerits, and there is no allocation method utilizing only the merits of both the methods.